


import java.util.Arrays;

public class Bucketsort {

public static void printarray(int [] parr){
	 for(int i = 0; i < parr.length; i++ ) {
	      System.out.print(parr[i] + " ");
	    }	
	System.out.println("");
}

  public static int[] bucketSort(int[] arr) {
    int i, j;
	int max=0;
   
//count
	for(i = 0; i < arr.length; i++ ) {
	      if(arr[i]>max){
				max=arr[i];
				
			}
	    }
	if(arr.length>max){
		max=arr.length;
		
	}
	 int[] count = new int[max+1];	
    for(i = 0; i < arr.length; i++ ) {
      count[arr[i]]++;
	
    }

    for(i=0,j=0; i < count.length; i++) {
      for(; count[i]>0; (count[i])--) {
		printarray(arr);
		
        arr[j++] = i;
      }
    }

    return arr;
  }


  public static void main(String[] args) {
    int[] arr = new int[] {1,3,4,6,10,2,9,1,2,12,4,6,7,8,100};
  
    printarray(arr);
   

    arr = bucketSort(arr);

    printarray(arr);
    System.out.println();

  }
}

